/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/2/18 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

import java.util.Arrays;

/**
 * @ProjectName: projectweb
 * @ClassName: guibing
 * @Description: 请描述该类的功能
 * @Author: 1913040634刘世锦
 * @Date: 2021/2/18 14:00 .
 * @version v1.0
 */
public class guibing {

        public static void main(String[] args) {
            int[] arr = {7,4,1,3,6,8,2,5};
            int[] temp = new int[arr.length];
            MergeSort(arr,0,arr.length-1,temp);
            System.out.println(Arrays.toString(arr));
        }

        //元素分解
        public static void MergeSort(int[] arr,int left,int right,int[] temp){
            if (left<right){
                //中间索引
                int mid = (left + right)/2;
                //递归左边进行分解
                MergeSort(arr,left,mid,temp);
                //递归右边进行分解
                MergeSort(arr,mid+1,right,temp);
                //到合并
                merge(arr,left,mid,right,temp);
            }
        }

        //元素合并
        public static void merge(int[] arr,int left,int mid,int right,int[] temp){

            //左边有序序列的初始索引
            int i = left;
            //右边有序序列的初始索引
            int j = mid+1;
            //指向temp的当前索引
            int t = 0;
            //先把左右两边的有序元素有序的拷贝到temp数组中
            while (i <= mid && j <= right){
                if (arr[i] <= arr[j]){
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else {
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
            }
            //把一边剩余的元素拷贝到temp数组中
            while (i <= mid){
                temp[t] = arr[i];
                t++;
                i++;
            }
            while (j <= right){
                temp[t] = arr[j];
                t++;
                j++;
            }

            //将temp数组中元素拷贝到arr数组中
            t = 0;
            int templeft = left;
            while (templeft <= right){  //for
                arr[templeft] = temp[t];
                templeft++;
                t++;
            }
        }
    }

